//2月3日
var removeDuplicates = function(nums) {
    if(nums.length==0){
         return;
     }
     // 定义一个左指针
     var left = 0;
     // 循环遍历数组
     for(var i = left+1;i<nums.length;i++){
         if(nums[left]!==nums[i]){
             left=left+1;
             nums[left]=nums[i];
         }
        continue;
     }
     nums.splice(left+1,nums.length-1);
     return nums
 };
 //2.4
 //检查是否为对称二叉树
 var isSymmetric=function(root){
    if(!root){return true}
    return mirror(root.left,root.right)
 }
 function mirror(node1,node2){
    if(!node1&&!node2) return true
    if(!node1||!node2) return false
    return (node1.val===node2.val)&&mirror(node1.left,node2.right)&&mirror(node1.right,node2.left)
 }
 //杨辉三角
 var getRow=function(rowIndex){
    let res=[[1]]
    if(rowIndex){
        for(let i=1;i<rowIndex;i++){
            res[i]=[]
            for(let j=0;j<i+1;j++){
                res[i][j]=(res[i-1][j||0])+(res[i-1][j-1||0])
            }
        }
        return res[rowIndex]
    }
    else{
        return [1]
    }
 }
 //合并两个有序数组
 var merge = function(nums1, m, nums2, n) {
    // write code here
        // 思路2
       let index = m + n -1
       let i = m - 1
       let j = n - 1
       while(i >= 0 && j >= 0) 
              // 思路3
              nums1[index --] = nums1[i] >= nums2[j] ? nums1[i --] : nums2[j --]
       // 思路4
       while(j >= 0) nums1[index --] = nums2[j --]
    };

    //相同的树
    var isSameTree = function(p, q) {
        return isSame(p,q);
    };
    var isSame=function(p,q){
        if(p == null && q == null) return true;
        if((!p && q) || (p && !q)) return false;
        if(p.val !== q.val) return false; // 需保证 p 和 q 都不是 null，否则报错
        let ll = isSame(p.left, q.left);
        let rr = isSame(p.right, q.right);
        return rr && ll;
    }
    //2.6
    //反转链表
    var reverseList = function (head){
        //声明变量记录prev、cur
        let prev = null
        let cur = head
        //当cur是节点时，进行迭代
        while(cur){
          //先保存当前节点的下一个节点
          const next = cur.next
          cur.next=prev
          prev = cur
          cur = next
        }
        return prev
      }
//快乐数
// 方法一
// 1. 通过循环不断的去判断  不确定循环多少次  只能用while  
// 2. 如果 循环过程中遇到4 或者 1 不用继续判断了 遇到4 一定不是 
// 遇到1 循环结束 
// 3.需要取每个数字的平方  每次取一个数字的个位  temp
// 132  第一次 2 剩下 13 第二次 3 剩下1  第三次1 剩下 0 
// 需要一个变量来存 132  13  1
// 4.我们需要一个变量来存放每个数字的平方   newNum
// 注意问题 newNum 如果不是1 并且 4 需要重新判断  也就是 newNum归零
function isHappyNumber(num){
    var newNum,temp; //准备一个变量存放临时数字
    // 132   变量第一次存132 第二次存 13 第三次存 1  0 
    while(num != 4 && num !=1){
        temp = num; // 
        newNum = 0;
        while(temp>0){
            newNum += Math.pow(temp%10,2);
            temp = parseInt(temp/10);
        }
        num = newNum;
        
    }
    return num == 1;  // 一定是布尔类型
}
//方法二
const getNumber = (n) => {
    let res = 0
    do {  
        const a = n % 10
        n = (n - a) / 10
        res += a * a
    } while( n >= 10)
    res += n * n
    return res
}

var isHappy = function(n) {
    let list = []
    while(true) {
      n = getNumber(n)
      if (n === 1) {
          return true
      } else if (list.indexOf(n) !== -1) {
         return false
      }
      list.push(n)
    }
};
//2.7
//青蛙跳台阶
var numWays = function(n) {
    //动态规划
      if(n===0){
          return 1;
      }
      const arr=[null,1,2];
      for(let i=3;i<=n;i++){
          arr[i]=(arr[i-1]+arr[i-2])%1000000007;
      }
      return arr[n]; 
     
  };
//从头到尾打印链表
var reversePrint = function(head) {
    let res = []
    while(head) {
        res.unshift(head.val);
        head = head.next;
    }
    return res
}

//2月8日
//圆圈剩下的数字
// m = 3, n = 2
// 首先最后一轮中num的下标一定是0， 这个是已知的。
// 那上一轮应该是有两个元素，此轮次中 num 的下标为 (0 + m)%n = (0+3)%2 = 1; 说明这一轮删除之前num的下标为1；
// 再上一轮应该有3个元素，此轮次中 num 的下标为 (1+3)%3 = 1；说明这一轮某元素被删除之前num的下标为1；
// 再上一轮应该有4个元素，此轮次中 num 的下标为 (1+3)%4 = 0；说明这一轮某元素被删除之前num的下标为0；
// 再上一轮应该有5个元素，此轮次中 num 的下标为 (0+3)%5 = 3；说明这一轮某元素被删除之前num的下标为3；
// ....

// 因为我们要删除的序列为0-n-1, 所以求得下标其实就是求得了最终的结果。比如当n 为5的时候，num的初始下标为3，
// 所以num就是3，也就是说从0-n-1的序列中， 经过n-1轮的淘汰，3这个元素最终存活下来了，也是最终的结果。

// 总结一下推导公式：(此轮过后的num下标 + m) % 上轮元素个数 = 上轮num的下标
var lastRemaining = function (n, m) {
    let ans = 0 // 最后一轮下标肯定为0
    // 往前推，最后一轮是1个人，那么再往前是两个人
    for (let i = 2; i <= n ; i++) {
      ans = (ans + m) % i
    }
    return ans
  }
  //链表是否有环
//   通过快慢指针实现,快指针一次前进两步,慢指针一次前进一步。
// 当链表中有环时,快慢指针总会相遇。
// 当快指针或者快指针的下一个元素为空时,就代表无环。
  var hasCycle = function(head) {
    let p1=head;
    let p2=head;
    while(p1&&p2&&p2.next){
        p1=p1.next;
        p2=p2.next.next;
        if(p1===p2){
            return true
        }
    }
    return false
};
//2月9日 旋转数组的最小数字
//首先，创建两个指针 left, right 分别指向 numbers 首尾数字，然后计算出两指针之间的中间索引值 middle，然后我们会遇到以下三种情况：
// middle > right ：代表最小值一定在 middle 右侧，所以 left 移到 middle + 1 的位置。
// middle < right ：代表最小值一定在 middle 左侧或者就是 middle，所以 right 移到 middle 的位置。
// middle 既不大于 left 指针的值，也不小于 right 指针的值，代表着 middle 可能等于 left 指针的值，或者 right 指针的值，我们这时候只能让 right 指针递减，来一个一个找最小值了。
var minArray = function(numbers) {
    let left=0;
    let right=numbers.length-1;
    while(left<right){
        var mid=left + Math.floor((right-left)/2);
        if(numbers[mid]>numbers[right]){
            left=mid+1;
        }else if(numbers[mid]<numbers[right]){
            right=mid;
        }else{
            right--;
        }
    }
    return numbers[left];
};

//删除链表的节点
function deleteNode( head ,  val ) {
    // write code here
    if(head.val===val)
        return head.next
    //设置一个pre前节点，以便删除操作
    var pre=null
    var p=head
    // 链表当前值与val值不相等时，一直向下找
    while(p.val !==val){
        pre = p;
        p = p.next;
    }
    //此时跳出循环，说明是找到了
    pre.next = p.next;
    return head
}
//2月10
//剪绳子
// 利用均值不等式求得 将绳子分成长度为3 的时候，乘积最大。
// 当最后一截绳子的长度不满足3的时候，
// - 若这一截绳子的长度为1，则拿将前一根绳子和这一根绳子凑起来分成两根长度为2 的绳子
// - 若这一截绳子的长度为2，则不做改动
var cuttingRope = function(n) {
    if(n===2||n===3){return n-1};  //当绳子的长度为2 或者 3 的时候，乘积返回的是n-1
    let a = n%3; // 这里取到 n 对 3 的余数
    let b = parseInt(n/3); // 这里取到  n 对 3 的整数
    if(a===0){ // 当 n 是 3 的倍数的时候
        return 3**b; // 返回的是整数个 3 的乘积
    }else if(a===1){ // 当 余数是 1 的时候
        return 2*2*(3**(b-1)) // 从前一个3 那里抽出一个3 拆分成两个 2 的乘积，所以3 的个数就是 b-1
    }else{
        return 2*(3**b) // 当余数为2 的时候，直接是 b 个3 乘以一个2 即可
    }
};
//2月11日
// 两数相加
var addTwoNumbers = function(l1, l2) {
    let head = null, tail = null;
    let carry = 0;
    while (l1 || l2) {
        const n1 = l1 ? l1.val : 0;
        const n2 = l2 ? l2.val : 0;
        const sum = n1 + n2 + carry;
        if (!head) {
            head = tail = new ListNode(sum % 10);
        } else {
            tail.next = new ListNode(sum % 10);
            tail = tail.next;
        }
        carry = Math.floor(sum / 10);
        if (l1) {
            l1 = l1.next;
        }
        if (l2) {
            l2 = l2.next;
        }
    }
    if (carry > 0) {
        tail.next = new ListNode(carry);
    }
    return head;
};
//2月12日
//无重复字符串的最大长度
var lengthOfLongestSubstring = function(s) {
    let l = 0;     //子串左边界位置
    let res = 0;   //最长连续无重复子串长
    const map = new Map();
    for(let r = 0; r < s.length ; r++) {
        //该字符存在map中并且在字串中 注意 abbcdea 这种情况
        if (map.has(s[r]) && map.get(s[r]) >= l) { 
            l = map.get(s[r]) + 1; //移动左边界至重复字符的下一个位置
        }
        res = Math.max(res, r-l+1);  //更新最长子串
        map.set(s[r], r);  //将该字符放入map
    }
    return res;
};
//2月13日
//数值的整数次幂
var myPow = function(x, n) {
    
    // !本题核心： 当n为奇数和偶数时两种情况的讨论
    // 情况1： (2,4) = (2,2) * (2,2)
    // 情况2：(2,5) = (2,2) * (2,2) * 2
    // 首先n是有可能为0，正，负数的
    if (n === 0) return 1;
    // 无论正负数我们都先将其转换为正数计算
    const res = dfs(x,Math.abs(n));

    if (n > 0) {
        return res;
    } else {
        return 1/res;
    }

    function dfs(x,n) {
        // 递归的结束条件
        if (n === 1) {
            return x;
        }
        let temp = dfs(x,Math.floor(n/2));

        return n % 2 ? (x * temp * temp) : (temp * temp)
    }
}
//2月14 重建二叉树
//  思路：递归，通过重建节点的左子树和右子树，实现对整个二叉树的重建，抓住前序遍历是’根左右‘，中序遍历是’左根右‘的特性，更新需要传给函数的前序遍历和中序遍历。
var buildTree = function(preorder, inorder) {
    if (!preorder.length || !inorder.length) return null
    const root = preorder[0]
    const i = inorder.indexOf(root)
    const node = {
        val: root,
        left: buildTree(preorder.slice(1, i + 1), inorder.slice(0, i)),
        right: buildTree(preorder.slice(i + 1), inorder.slice(i + 1)),
    }
    return node
};
//2月15日 组合总数
//这道题思路是主要还是利用回溯+剪枝的过程构造一棵树，其中叶子节点就是最终的结果，我们可以先将数组排序并筛选剔除，减少迭代的次数
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    var arr = candidates.filter(function(i) {    //剔除大于target的数
        return i <= target;
    })
    arr.sort(function(a, b){
        return a-b;
    });
	if (arr.length === 0) return [];   //剔除后数组为空
    if (arr[0] === target) return [[target]];   //最小的数等于target

    var map = {};
    var ans = [];
    for (var i=0; i<arr.length; i++){
        getSum(arr[i], '' + arr[i]);
    }

    function getSum(num, str) {
        if (num > target) return;

        if (num === target) { 
            ans.push(str.split('-'));
            return;
        }

        for (var i=0; i<arr.length; i++){
            getSum(num+arr[i], str + '-' + arr[i]);
        }
    }

    return ans.filter(function(i) {
        i.sort(function(a, b){
            return a-b;
        });
        var key = i.join('');
        if (map[key]) return false;
        map[key] = true;
        return true;
    });
};
//2月16日
//整数转罗数字   使用Math.floor()
/**
 * @param {number} num
 * @return {string}
 */
var intToRoman = function(num) {
    var thousands = ['','M','MM','MMM'];
    var hundreds = ['','C','CC','CCC','CD','D','DC','DCC','DCCC','CM'];
    var tens = ['','X','XX','XXX','XL','L','LX','LXX','LXXX','XC'];
    var ones = ['','I','II','III','IV','V','VI','VII','VIII','IX'];
    num = num.toString();
    if( num.length == 1){
        return ones[num%10];
    }else if(num.length == 2){
        return tens[Math.floor(num % 100 / 10)]+ones[num%10]
    }else if(num.length == 3){
        var h = hundreds[Math.floor(num / 100)];
        var t = tens[Math.floor(num % 100 / 10)];
        var o = ones[num%10];
        return h + t + o;
    }else{
         return thousands[Math.floor(num / 1000)]+hundreds[Math.floor(num % 1000 / 100)]+tens[Math.floor(num % 100 / 10)]+ones[num%10]
    }
   
};
//2月17日 电话号码和字母的组合
// 本题采用的是DFS的解题思路。
// 本题的特点在于递归中有循环。
// DFS函数接收两个参数，一个是当前字符串，一个是指针，当指针超过了digits的长度的时候，说明可以存储并返回了，然后上一层循环继续遍历下一个字符，真的很奇妙。
var letterCombinations = function(digits) {
    // 边界条件
    if (digits === '') return [];
    // 构建2-9对应字符的哈希表
    const m = new Map();
    m.set('2','abc');
    m.set('3','def');
    m.set('4','ghi');
    m.set('5','jkl');
    m.set('6','mno');
    m.set('7','pqrs');
    m.set('8','tuv');
    m.set('9','wxyz');
    
    // 定义返回的数组
    const res = [];
    // 使用DFS的思想
    function dfs(str,pointer) {
        // 递归的结束条件
        if (pointer > digits.length-1) {
            res.push(str);
            return;
        }
        let letters = m.get(digits[pointer]);
        for (let v of letters) {
            dfs(str + v,pointer + 1);
        }
        return;
    }
    dfs('',0)
    return res
};
//2月18日
//全排列
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
function permute(nums) {
    const res = [], path = [];
    const used = new Array(nums.length).fill(false);
    const dfs =()=> {
        if (path.length === nums.length) { // 递归出口：当path的长度等于length
            res.push(path.slice()); // 把path的一份拷贝加入到最后的结果res中，然后返回
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue; // 如果之前已经出现过了，直接跳过
            path.push(nums[i]);
            used[i] = true; // 表示这个位置已经用过了
            dfs(); // 递归 回溯
            path.pop(); // 回溯的过程中，将当前的节点从 path 中删除
            used[i] = false;
        }
    }
    dfs();
    return res;
}
//2月19日 二叉树的最大深度
// 思想和最小深度一样，递归的找到左右子树的最大深度，然后加上自身即可。注意最小深度需要考虑单侧节点为空的情况。
// 方法一：
var maxDepth = function(root) {
    if(!root) return 0

    let left = maxDepth(root.left)
    let right = maxDepth(root.right)

    return Math.max(left,right)+1
};
// 方法二
var maxDepth = function (root) {
  let res = 0;
  const dfs = (n, l) => {
    if (!n) { return; }
    if (!n.left && !n.right) {
      res = Math.max(res, l);
    }
    dfs(n.left, l + 1);
    dfs(n.right, l + 1);
  }
  dfs(root, 1);
  return res;
};
//2月20日
//删除链表倒数第n个节点
var removeNthFromEnd = function(head, n) {
    //创建虚拟节点，next指向head
    let node=new ListNode(0,head)
    //定义快慢指针都指向node
    let s=k=node
    //k需要比s快n+1,因为删除节点，需要找到前一个节点
    while((n+1)>0){
        k=k.next
        n--
    }
    while(k){
        k=k.next
        s=s.next
    }
    //删除s+1的节点
    s.next=s.next.next
    return node.next
};
//2月21日
//颜色分类 双指针
var sortColors = function(nums) {
    let n = nums.length;
    let p0 = 0, p1 = 0;
    for(let i = 0; i < n; ++i) {
        if(nums[i] === 1) {
            let temp = nums[i];
            nums[i] = nums[p1];
            nums[p1] = temp;
            p1++;
        } else if(nums[i] === 0) {
            temp = nums[i];
            nums[i] = nums[p0];
            nums[p0] = temp;
            if(p0 < p1) {
                temp = nums[i];
                nums[i] = nums[p1];
                nums[p1] = temp;
            }
            p0++;
            p1++;
        }
    }
};
//买卖股票的最佳时期
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let maxProfit = 0;
 let minPrice = prices[0];

 for (let i=1; i<prices.length; i++) {
   if (prices[i] < minPrice) {
     minPrice = prices[i];
   } else {
     maxProfit = Math.max(maxProfit, prices[i] - minPrice);
   }
 }

 return maxProfit;

};
//2月23日 路径的总和
// 上深度搜索模板，最终的判断条件是当前节点为叶子节点并且值和targetSum相等，递归时每次传入的targeSum需要减去当前节点的值。
var hasPathSum = function(root, targetSum) {
    if (root == null) {
        return false;
    } else if(root.left ==null && root.right == null){
        return targetSum==root.val;
    }else{
        return hasPathSum(root.left,targetSum-root.val) || hasPathSum(root.right,targetSum-root.val);
    }
};
//2月24日 整数反转
var reverse = function(x) {
    var s = x.toString();
    var str = "";
    for(var i = s.length - 1; i >= 0; i--){
        str += s[i];
    }
    if(str.indexOf('-') > 0){
        str = '-' + str.slice(0,s.length-1);
    }
    let ans = parseFloat(str);
    if(ans > Math.pow(2,31)-1 || ans < Math.pow(-2,31)){
        return 0;
    }else{
            return ans;
    }
    
};
//2月25 二叉搜索树与双向链表js
var treeToDoublyList = function(root) {
    if (!root) return null
    if (!root.left && !root.right) {
        root.left = root
        root.right = root
        return root
    }
    let firstNode = null
    let lastNode = null
    let prevNode = null
    function order(node) {
        if (!node) return
        order(node.left)
        if (!firstNode) firstNode = node
        if (!prevNode) {
            prevNode = node
        } else {
            prevNode.right = node
            prevNode = node
        }
        order(node.right)
    }
    order(root)
    let node = firstNode
    while (node.right) {
        node.right.left = node
        node = node.right
        lastNode = node
    }
    firstNode.left = lastNode
    lastNode.right = firstNode
    return firstNode
};
//2月26日 括号生成
/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    function node(str, left, right) {
        this.val = str;
        this.leftChild = null;
        this.rightChild = null;
        this.left = left;       //还剩余左括号的数量
        this.right = right;     //还剩余右括号的数量
    }

    function traverse(treeNode, result) {
        let {left, right, val} = treeNode;

        if (left === 0 && right === 0) {    //括号用完，推入结果
            result.push(val);
            return;
        }

        if (left === 0 && right > 0) {    //左括号用完，只能加右括号
            treeNode.rightChild = new node(val + ')', left, right - 1);
            traverse(treeNode.rightChild, result);
            return;
        }

        if (left === right) {       //当前剩余的左括号和右括号数量相等，则新括号必须为左括号
            treeNode.leftChild = new node(val + '(', left - 1, right);
            traverse(treeNode.leftChild, result);
            return;
        }

        if (left < right) {     //其余情况既可以添加左括号，又可以添加右括号
            treeNode.leftChild = new node(val + '(', left - 1, right);
            traverse(treeNode.leftChild, result);
            treeNode.rightChild = new node(val + ')', left, right -1);
            traverse(treeNode.rightChild, result);
        }
    }

    const root = new node('(', n-1, n);
    const result = [];
    traverse(root, result);
    return result;
};
//2月27 最长回文子串
var longestPalindrome = function(s) {
    let res = ''
    for (let i = 0; i < s.length; i ++) {
        let left = i - 1, right = i + 1 // s为奇数长度
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            left --, right ++
        }
        if (res.length < right - left - 1) {
            res = s.substring(left + 1, right)
        }
 
        left = i, right = i + 1 // s为偶数长度
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            left --, right ++
        }
        if (res.length < right - left - 1) {
            res = s.substring(left + 1, right)
        }
    }
    return res
};
//2月28日跳跃游戏
//思路：
// 若从第三位置可以跳到第五位置，那只要前面有一个点能跳到第三位置即可说明整体能跳到第五位置。
// 终点为最后一个点开始，看终点的前面是否存在一个点能跳到终点，若有这个点，此时终点为这个点，继续同样逻辑。
var canJump = function(nums) {
    let distance = nums.length - 1
    for (let i = nums.length - 2; i >= 0; i --) {
        if (nums[i] + i >= distance) {
            distance = i
        }
    }
    return distance === 0
};
//3月1 找出给定方程的正整数解
const findSolution = (customfunction, z) => {
    const result = [];
    for (let i = 1; i <= z; i++) {
      for (let j = 1; j <= z; j++) {
        if (customfunction.f(i, j) === z) {
          result.push([i, j]);
        }
      }
    }
    return result;
  };
//3月21
//遍历比较，设置一个最长的连续序列长度和一个当前遍历最长连续的长度
var longestConsecutive = function(nums) {
    var maxlen = 0 //最长连续序列长度
    var currlen = 1 //当前最长连续序列长度
    nums.sort((a,b) => a-b) //升序排序
    if(nums.length == 0){
        return 0
    }
    for(var i=0;i<nums.length;i++){
        if((nums[i] - 1) > nums[i-1]){//当出现不连续时，将currlen值初始化
            currlen =  1
        }
        else if((nums[i] - 1) == nums[i-1]){ //连续时，currlen值连续加1
            currlen = currlen + 1
        }
        if(currlen > maxlen){
            maxlen = currlen
        }
    }
    return maxlen
};
//3月22日 剑指 Offer 16. 数值的整数次方
var myPow = function(x, n) {
    // !本题核心： 当n为奇数和偶数时两种情况的讨论
    // 情况1： (2,4) = (2,2) * (2,2)
    // 情况2：(2,5) = (2,2) * (2,2) * 2
    // 首先n是有可能为0，正，负数的
    if (n === 0) return 1;
    // 无论正负数我们都先将其转换为正数计算
    const res = dfs(x,Math.abs(n));

    if (n > 0) {
        return res;
    } else {
        return 1/res;
    }

    function dfs(x,n) {
        // 递归的结束条件
        if (n === 1) {
            return x;
        }
        let temp = dfs(x,Math.floor(n/2));

        return n % 2 ? (x * temp * temp) : (temp * temp)
    }
}
//3月23 打印从1到最大的n位数
var printNumbers = function(n) {
    var len = Math.pow(10,n);
    var arr = [];
    for(var i = 1; i < len; i++){
        arr.push(i);
    }
    return arr;
};
